package com.xyz.study.algorithms;

/**
 * 算法实例
 * @author XYZ
 * @version 1.0.0
 * @since 2021-01-11 21:28
 */
public class AlgorithmsSimple {

    /**
     * 欧几里得算法
     * 计算两个非负整数p和q的最大公约数：
     * 若q是0，则得到的最大公约数为p。否则，将p除以q得到的余数r，p和q的最大公约数即为q和r的最大公约数
     * 附：约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。
     * @return 最大公约数
     */
    public static int gcd(int p, int q){
        if (q == 0){
            return q;
        }
        int r = p % q;
        return gcd(q, r);
    }

    /**
     * 动态规划算法 实现斐波那契数列
     */
    public static int fib(int n){
        int[] tmp = new int[n+1];
        for (int i = 0; i < n + 1; ++i){
            if (i < 2){
                tmp[i] = i;
            }else {
                tmp[i] = tmp[i-1] + tmp[i-2];
            }
        }
        return tmp[n];
    }
    public static void main(String[] args) {
        System.out.println(20%10);
        System.out.println(fib(5));
    }
}
